package leetcode;

/**
 * 331. 验证二叉树的前序序列化
 * 序列化二叉树的一种方法是使用前序遍历。当我们遇到一个非空节点时，我们可以记录下这个节点的值。如果它是一个空节点，我们可以使用一个标记值记录，例如 #。
 *      _9_
 *     /   \
 *    3     2
 *   / \   / \
 *  4   1  #  6
 * / \ / \   / \
 * # # # #   # #
 * 例如，上面的二叉树可以被序列化为字符串 "9,3,4,#,#,1,#,#,2,#,6,#,#"，其中 # 代表一个空节点。
 * 给定一串以逗号分隔的序列，验证它是否是正确的二叉树的前序序列化。编写一个在不重构树的条件下的可行算法。
 * 每个以逗号分隔的字符或为一个整数或为一个表示 null 指针的 '#' 。
 * 你可以认为输入格式总是有效的，例如它永远不会包含两个连续的逗号，比如 "1,,3" 。
 * 示例 1:
 * 输入: "9,3,4,#,#,1,#,#,2,#,6,#,#"
 * 输出: true
 * 示例 2:
 * 输入: "1,#"
 * 输出: false
 * 示例 3:
 * 输入: "9,#,#,1"
 * 输出: false
 */

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.EmptyStackException;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Stack;

public class problems_332 {
    public static void main(String[] args) {
        System.out.println(new Solution().isValidSerialization("1,#,#"));
    }

    static class Solution {
        public boolean isValidSerialization(String preorder) {
            String[] array = preorder.split(",");
            if (array.length == 0) return false;
            // 节点放入
            Stack<String> stack = new Stack<>();
            for (int i = array.length -1; i >= 0; i--) {
                stack.push(array[i]);
            }
            // 遍历
            Node root = new Node(stack.pop());
            boolean bol = dfs(root, stack);
            return stack.isEmpty() ? bol : false;
        }
        // 遍历部署
        public boolean dfs(Node node, Stack<String> stack){
            if ("#".equals(node.val)) return true;
            // 左节点
            if (stack.isEmpty()) return false;
            Node left = new Node(stack.pop());
            node.left = left;
            if(!dfs(left, stack)) return false;
            // 右节点
            if (stack.isEmpty()) return false;
            Node right = new Node(stack.pop());
            node.right = right;
            if(!dfs(right, stack)) return false;
            return true;
        }
        class Node {
            Node(String val){
                this.val = val;
            }
            public String val;
            public Node left;
            public Node right;
        }
    }
}